package com.practice.niuke.new_direct_basics.class13;

/**
 * 怎么求一棵树上，最大的二叉搜索子树的大小:
 *
 * 搜索二叉树：左树比自己小，右树比自己大。（严格定义！）
 *
 * 解法：二叉树的dp套路
 *
 * 列可能性：
 * 以x节点为头的树，可以向其左树和右树要信息的情况下，求得这棵树上最大的二叉搜索子树的大小的可能性如下，
 * （1）与x自己无关
 * 1. 与x节点自己无关，说明以x节点为头的整棵树不是搜索二叉树。
 * 2. 这个时候以x为头的整棵树的最大搜索二差子树的大小为，
 * max{左树上最大二叉搜索子树的大小， 右树上最大二叉搜索子树的大小}
 * （2）与x自己有关
 * 1. 与x节点自己有关，说明以x节点为头的整棵树是搜索二叉树。
 * 2. 以x节点为头的整棵树是搜索二叉树的条件：
 * a. 以x节点为头的整棵树，左树整体为搜索二叉树
 * b. 以x节点为头的整棵树，右树整体为搜索二叉树
 * c. 以x节点为头的整棵树，左树上的最大值 < x的值 && 右树上的最小值 > x的值
 * 3. 以x节点为头的整棵树是搜索二叉树时， 左树节点的个数就是左树上最大搜索二叉树的大小，
 * 右树节点的个数就是右树上最大搜索二叉树的大小，整棵树的最大搜索二差子树的大小为，
 * 左树的节点个数+1+右树的节点个数 == 左树上最大搜索二叉树的大小 + 1 + 右树上最大搜索二叉树的大小。
 *
 * 为了支持上面的各种可能性，需要的信息汇总过程，
 * 1. 左树需要如下信息：
 * （1）左树上最大搜索二叉树的大小
 * （2）左树是否为搜索二叉树
 * （3）左树上的最大值
 * 2. 右树需要如下信息
 * （1）右树上最大搜索二叉树的大小
 * （2）右树是否为搜索二叉树
 * （3）右树上的最小值
 *
 * 左树和右树要的信息不一样，求全集（并集）得到信息体：
 * （1）整棵树的 最大搜索二叉子树的大小
 * （2）整棵树 是否为搜索二叉树
 * （3）整棵树的 最大值
 * （4）整棵树的 最小值
 */
public class MaxBSTSize {

    public static class Node {
        public int value;
        Node left;
        Node right;
    }

    /**
     * 主流程
     *
     * @param head head
     * @return
     */
    public static int maxBST(Node head) {
        return process(head).maxBSTSize;
    }

    /**
     * 信息体（对于任意一棵树）
     */
    public static class Info {
        // 当前这棵树的最大二叉搜索子树的大小
        public int maxBSTSize;
        // 当前这棵树是否为搜索二叉树
        public boolean isBST;
        // 当前这棵树上的最小值
        public int min;
        // 当前这棵树生的最大值
        public int max;

        public Info(int maxBST, boolean is, int mi, int ma) {
            maxBSTSize = maxBST;
            isBST = is;
            min = mi;
            max = ma;
        }
    }

    /**
     * 以x为头的子树的递归流程，返回要求的所有信息，Info
     *
     * @param x x
     * @return Info
     */
    public static Info process(Node x) {
        if (x == null) { // base case
            return null;
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int min = Math.min(x.value, Math.min(leftInfo == null ? Integer.MAX_VALUE : leftInfo.min,
                rightInfo == null ? Integer.MAX_VALUE : rightInfo.min));
        int max = Math.max(x.value, Math.max(leftInfo == null ? Integer.MIN_VALUE : leftInfo.max,
                rightInfo == null ? Integer.MIN_VALUE : rightInfo.max));

        boolean isBST = false;
        // 先假设 与x自己无关
        int maxBSTSize = Math.max(leftInfo == null ? 0 : leftInfo.maxBSTSize,
                rightInfo == null ? 0 : rightInfo.maxBSTSize); // p1, p2
        if (
            // 左树为搜索二叉树（左树为null时是搜索二叉树，左树不为null时就取leftInfo.isBST）
            leftInfo == null ? true : leftInfo.isBST
                    &&
            // 右树为搜索二叉树（右树为null时是搜索二叉树，右树不为null时就取rightInfo.isBST）
            rightInfo == null ? true : rightInfo.isBST
                    &&
            // 左树的最大值小于x的值
            leftInfo.max < x.value
                    &&
            // 右树的最小值大于x的值
            rightInfo.min > x.value
        ) {
            // 与x自己有关
            maxBSTSize = (leftInfo == null ? 0 : leftInfo.maxBSTSize) + 1 + (rightInfo == null ? 0 : rightInfo.maxBSTSize);
            isBST = true;
        }
        return new Info(maxBSTSize, isBST, min, max);
    }

}
